home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / macros / latex209 / contrib / misc / trees.sty < prev    next >
Text File  |  1993-01-11  |  7KB  |  121 lines
  1. %        treedef.tex
  2. %
  3. %    These definitions for tree macros are taken from "Trees in TeX",
  4. %    by David Eppstein, as published in TUGboat 6#1, March 1985.
  5. %    David Eppstein's address (as of 15 June 1988) is
  6. %        Computer Science Department
  7. %        Columbia University
  8. %        New York, NY 10027
  9. %        Eppstein@cs.Columbia.edu
  10.  
  11. \newbox\treebox
  12. \def\tree{\global\setbox\treebox=\boxtree}
  13. \def\subtree{\ettext \boxtree}
  14. \def\leaf#1{\subtree#1\endsubtree}
  15.  
  16. \def\endsubtree{\ettext \egroup}
  17. \def\endtree{\endsubtree \settreesizes \typesettree}
  18.  
  19. \newif\iftreetext\treetextfalse         % Whether still aligning text
  20. \def\boxtree{\hbox\bgroup               % Start outer box of tree or subtree
  21.   \baselineskip 2.5ex                   % Narrow line spacing slightly
  22.   \tabskip 0pt                          % No spurious glue in alignment
  23.   \vbox\bgroup                          % Start inner text \vbox
  24.   \treetexttrue                         % Remember for \ettext
  25.   \let\par\crcr \obeylines              % New line breaks without explicit \cr
  26.   \halign\bgroup##\hfil\cr}             % Start alignment with simple template
  27. \def\ettext{\iftreetext                 % Are we still in inner text \vbox?
  28.   \crcr\egroup \egroup \fi}             % Yes, end alignment and box
  29.  
  30. \def\cons#1#2{\edef#2{\xmark #1#2}}     % Add something to start of list.
  31. \def\car#1{\expandafter\docar#1\docar}  % Take first element of list
  32. \def\docar\xmark#1\xmark#2\docar{#1}    % ..by ignoring rest in expansion.
  33. \def\cdr#1{\expandafter\docdr#1\docdr#1} % Similarly, drop first element.
  34. \def\docdr\xmark#1\xmark#2\docdr#3{\def#3{\xmark #2}}
  35. \def\xmark{\noexpand\xmark}             % List separator expands to self.
  36. \def\nil{\xmark}                        % Empty list is just a separator.
  37.  
  38. \def\settreesizes{\setbox0=\copy\treebox \global\let\treesizes\nil \setsizes}
  39. \newdimen\treewidth                     % Width of this part of the tree.
  40. \def\setsizes{\setbox0=\hbox\bgroup     % Get a horiz list as a workspace.
  41.   \unhbox0\unskip                       % Take tree, unpack it into horiz list.
  42.   \inittreewidth                        % Get old width at this level.
  43.   \sizesubtrees                         % Recurse through all subtrees.
  44.   \sizelevel                            % Now set width from remaining \vbox.
  45.   \egroup}                              % All done, finish our \hbox.
  46.  
  47. \def\inittreewidth{\ifx\treesizes\nil   % If this is the first at this level
  48.     \treewidth=0pt                      % ..then we have no previous max width.
  49.   \else \treewidth=\car\treesizes       % Otherwise take old max level width
  50.     \global\cdr\treesizes               % ..and advance level width storage
  51.     \fi}                                % ..in preparation for next level.
  52.  
  53. \def\sizesubtrees{\loop                 % For each box in horiz list (subtree)
  54.   \setbox0=\lastbox \unskip             % ..pull it off list and flush glue.
  55.   \ifhbox0 \setsizes                    % If hbox, it's a subtree - recurse
  56.   \repeat}                              % ..and loop; end loop on tree text.
  57.  
  58. \def\sizelevel{\ifdim\treewidth<\wd0    % If greater than previous maximum
  59.    \treewidth=\wd0 \fi                  % Then set max to new high
  60.  \global\cons{\the\treewidth}\treesizes}% In either case, put back on list
  61.  
  62. \newdimen\treeheight                    % Height of this part of the tree.
  63. \newif\ifleaf                           % Tree has no subtrees (is a leaf).
  64. \newif\ifbotsub                         % Bottom subtree of parent.
  65. \newif\iftopsub                         % Top subtree of parent.
  66. \def\typesettree{\medskip \maketree \medskip}   % Make whole tree with spacing.
  67. \def\maketree{\hbox{\treewidth=\car\treesizes   % Get width at this level.
  68.   \cdr\treesizes                        % Set up width list for recursion.
  69.   \makesubtreebox\unskip                % Set \treebox to text, make subtrees.
  70.   \ifleaf \makeleaf                     % No subtrees, add glue.
  71.   \else \makeparent \fi}}               % Have subtrees, stick them at right.
  72.  
  73. {\catcode`@=11                          % Be able to use \voidb@x.
  74. \gdef\makesubtreebox{\unhbox\treebox    % Open up tree or subtree.
  75.   \unskip\global\setbox\treebox\lastbox % Pick up very last box.
  76.   \ifvbox\treebox                       % If we're already at the \vbox
  77.     \global\leaftrue \let\next\relax    % ..then this is a leaf.
  78.   \else \botsubtrue                     % Otherwise, we have subtrees.
  79.     \setbox0\box\voidb@x                % Init stack of processed subs
  80.     \botsubtrue \let\next\makesubtree   % ..and call \maketree on them.
  81.   \fi \next}}                           % Finish up for whichever it was.
  82.  
  83. \def\makesubtree{\setbox1\maketree      % Call \maketree on this subtree.
  84.   \unskip\global\setbox\treebox\lastbox % Pick up box before it.
  85.   \treeheight=\ht1                      % Get height of subtree we made
  86.   \advance\treeheight 2ex               % Add some room around the edges
  87.   \ifhbox\treebox \topsubfalse          % If picked up box is a \vbox,
  88.     \else \topsubtrue \fi               % ..this is the top, otherwise not.
  89.   \addsubtreebox                        % Stack subtree with the rest.
  90.   \iftopsub \global\leaffalse           % If top, remember not a leaf
  91.     \let\next\relax \else               % ..(after recursion), set return.
  92.     \botsubfalse \let\next\makesubtree  % Otherwise, we have more subtrees.
  93.   \fi \next}                            % Do tail recursion or return.
  94.  
  95. \def\addsubtreebox{\setbox0=\vbox{\subtreebox\unvbox0}}
  96. \def\subtreebox{\hbox\bgroup            % Start \hbox of tree and lines
  97.   \vbox to \treeheight\bgroup           % Start \vbox for vertical rules.
  98.     \ifbotsub \iftopsub \vfil           % If both bottom and top subtree
  99.         \hrule width 0.4pt              % ..vertical rule is just a dot.
  100.       \else \treehalfrule \fi \vfil     % Bottom gets half-height rule.
  101.     \else \iftopsub \vfil \treehalfrule % Top gets half-height the other way.
  102.       \else \hrule width 0.4pt height \treeheight \fi\fi % Middle, full height.
  103.     \egroup                             % Finish vertical rule \vbox.
  104.   \treectrbox{\hrule width 1em}\hskip 0.2em\treectrbox{\box1}\egroup}
  105.  
  106. \def\treectrbox#1{\vbox to \treeheight{\vfil #1\vfil}}
  107. \def\treehalfrule{\dimen0=\treeheight   % Get total height.
  108.   \divide\dimen0 2\advance\dimen0 0.2pt % Divide by two, add half horiz height.
  109.   \hrule width 0.4pt height \dimen0}    % Make a vertical rule that high.
  110.  
  111. \def\makeleaf{\box\treebox}             % Add leaf box to horiz list.
  112. \def\makeparent{\ifdim\ht\treebox>\ht0  % If text is higher than subtrees
  113.     \treeheight=\ht\treebox             % ..use that height.
  114.   \else \treeheight=\ht0 \fi            % Otherwise use height of subtrees.
  115.   \advance\treewidth-\wd\treebox        % Take remainder of level width
  116.   \advance\treewidth 1em                % ..after accounting for text and glue.
  117.   \treectrbox{\box\treebox}\hskip 0.2em % Add text, space before connection.
  118.   \treectrbox{\hrule width \treewidth}\treectrbox{\box0}} % Add \hrule, subs.
  119.  
  120. \endinput
  121.